package org.hot100_1;

import java.util.Arrays;

public class leetcode82 {
//    public int lengthOfLIS(int[] nums) {
//
//        //dp[i]的意义是，以nums[i]为结尾的数字的最大子序列长度
//        int [] dp = new int[nums.length];
//
//        Arrays.fill(dp,1);
//
//        int res = 1;
//        //外部循环从1开始和从0开始效果一样
//        for (int i = 1; i < nums.length; i++) {
//            //内部需要遍历i之前的数字，判断是否存在小于num[i]的值，如果存在，需要更新dp[i]的值
//            //内部使用j<i和j<=i效果相同，使用j<=i，在当j=i时，在后续的判断中不会修改dp[i]的值。
//            for (int j = 0; j <i; j++) {
//                if (nums[j]<nums[i]){
//                    //dp[i]的值在内部循环中会被修改多次，dp[i]可以理解为在这次循环中没有选择nums[j]
//                    //dp[j]+1表示：在以nums[j]为结尾的子序列上添加num[i]，所以要加1。可以理解为在本次循环中选择了nums[j]
//                    dp[i]=Math.max(dp[i],dp[j]+1);
//                }
//            }
//            res = Math.max(res,dp[i]);
//        }
//
//        return res;
//    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        //dp[i]表示nums[i]为结尾的子序列最大长度
        int max =1;
        int [] dp =new int[n];
        Arrays.fill(dp,1);
        for (int i = 1; i <n; i++) {
            for (int j = 0; j <=i; j++) {
                if (nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            max=Math.max(max,dp[i]);
        }

        return max;
    }
}
